The prior art discloses various data processing systems which employ a virtual memory arrangement for storing information. Virtual storage extends the power of computer storage by expanding the number of storage addresses that can be represented in a system while relieving the limitation that all addressable storage must be present in the main memory of the system. The address translation mechanism, which functions to translate a virtual address to an address in real memory requires data structures such as page tables fixed in memory to perform the address translation function.
In some prior art systems, the size of the conventional page table is proportional to the size of the virtual address space which places a practical limit on the number of address locations in virtual memory which, in turn, effectively limits the size or storage capacity of the virtual memory.
Other prior art systems employ a technique referred to as "paged segmentation" for the virtual memory. The cross-referenced application describes a virtual memory which employs a paged segmentation technique. In that arrangement, the effective address space was divided into 16 equal sized segments by the memory management unit, and the 32 bit effective address generated by the processor was converted to a 40 bit virtual address by using 4 bits of the effective address to select 1 of 16 segment registers, each of which stores a 12 bit segment identifier. The 12 bit segment identifier concatenated with the 28 bit segment offset comprises the 40 bit virtual address which defines one addressable location for one byte of data. The division of the virtual address space into segments, and then into pages, is what is referred to as "page segmentation."
A segment stores an object such as program, a mapped file, or computational data. A data structure referred to as the segment table defines the objects that can be currently referenced by the system, and provides information such as the object size and the location where its external page table is stored. The external page table for the segment has one entry for each page in the segment. Page segmentation is a means of improving the overall operation of the memory system. It takes advantage of the grouping of related data in virtual storage by representing page table data, specifically for each segment. This allows space savings for short or unused segments. The other data structure used by prior art systems is the inverted page table. An inverted page table further expands the range of addressability by reducing the real storage overhead required to support a very large virtual address space. Since an inverted page table contains one entry for each page of real memory, its overhead is proportional to the physical, rather than virtual memory size. This makes it feasible to map a system's entire data base using a single set of virtual addresses (the "one level store"). With a one level store, each segment can be large enough to represent an entire file or collection of data.
This is possible because the address translation hardware only needs the location of pages that are present in real memory. If a page is not present, the hardware must detect this fact, but it does not require a backing store address. The system's paging subsystem does need this information, however. Hence, the paging subsystem must keep this information in some data structure, such as the external page table that is associated with the page. Unless this data structure is pageable, the advantage of the inverted page table is lost because the pinned real storage requirements become proportional to virtual memory size.
The function of the paging subsystem is fundamentally to manage pages of virtual memory and page frames of real memory. Each of these items will have well defined states which change as they are processed through the system. The data structures that keep track of these states must be updated to reflect each changed state. Since independent system events can cause the state of a page or page frame to be changed, it is important to ensure that the state changes caused by one system event are reflected in the appropriate data structures before the next system event is permitted to execute a state change.
In other words, the system events that change page states and require updates to data structures that reflect states of pages and page frames, must be logically serialized. Such events depend to some extent on the architecture of the system, particularly the memory management function and the page fault mechanism, but generally fall into three categories:
(1) page fault interrupts; PA1 (2) paging I/O completion interrupts; PA1 (3) supervisory calls to paging services, i.e., creating or destroying a segment.
Without this serialization, the integrity of the data structures could not be guaranteed.
A virtual machine, virtual memory type data processing system is described in the cross-referenced applications and is generally the type of system in which the method of the present invention may be employed to insure that the system events that change or update data structures that store the current status of the virtual pages and page frames are logically serialized so that the integrity of these data structures is maintained. The general architecture of that system is similar to prior art systems from the standpoint of the need to serialize those system events that cause data structures to be changed in order to reflect the current state of pages and page frames.
Briefly, in systems of the above type, pages can assume a plurality of different states, such as the five states described below.
(1) new
The virtual page is known to be all zeros. Each virtual page is initialized to this state when a segment is created or increased in size.
(2) accessible
The virtual page may be accessed without resulting in a page fault. This is the only page state that allows a virtual page to be accessed without resulting in a page fault.
(3) hidden
The virtual page is hidden from program access and any access to the page will result in a page fault.
(4) on disk
The virtual page is only valid on disk. It does not have a page frames assigned to it.
Page frames can also assume a plurality of different states, such as the four described below.
(1) in use
Page frames in this state are assigned to a virtual page.
(2) free
Page frames in this state are free to be assigned to a new virtual page.
(3) page-in
Page frames with page-in I/O in progress.
(4) page-out
Page frames with page-out I/O in progress.
Data structures employed by these systems to maintain the current status of virtual pages and page frames include, for example, a segment table, an External Page Table, and an Inverted Page Table. These structures generally have the following functions: